package gold.digger;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC76 {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> curWindow = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            addChar(need, t.charAt(i));
        }

        int left = 0, right = -1, satisfy = 0, minLength = Integer.MAX_VALUE;
        String result = "";
        while (right < s.length() - 1) {
            char ch = s.charAt(++right);
            // judge satisfy.
            if (need.containsKey(ch)) {
                addChar(curWindow, ch);
                if (need.get(ch).intValue() == curWindow.get(ch).intValue()) {
                    ++satisfy;
                }
            }

            // process back.
            while (satisfy >= need.size()) {
                if (right - left < minLength) {
                    result = s.substring(left, right + 1);
                    minLength = right - left;
                }

                char back = s.charAt(left++);
                if (need.containsKey(back)) {
                    if (curWindow.containsKey(back) &&
                            need.get(back).intValue() == curWindow.get(back).intValue()) {
                        --satisfy;
                    }
                    minusChar(curWindow, back);
                }
            }
        }

        return result;
    }

    public void addChar(Map<Character, Integer> map, char ch) {
        if (map.containsKey(ch)) {
            map.put(ch, map.get(ch) + 1);
        } else {
            map.put(ch, 1);
        }
    }

    public void minusChar(Map<Character, Integer> map, char ch) {
        Integer count = map.get(ch);
        if (null == count) {
            return;
        }

        if (1 == count.intValue()) {
            map.remove(ch);
            return;
        }

        map.put(ch, count.intValue() - 1);
    }


    public static void main(String[] args) {
        LC76 an = new LC76();
        System.out.println(an.minWindow("AA", "A"));
    }
}
